//https://leetcode.cn/problems/palindrome-linked-list-lcci/

struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* newhead = NULL;
    struct ListNode* cur = head;

    //头插
    while (cur)
    {
        struct ListNode* next = cur->next;
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }

    return newhead;
}

struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* slow, * fast;
    slow = head;
    fast = head;

    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }

    return slow;
}

bool isPalindrome(struct ListNode* head) {

    struct ListNode* mid = middleNode(head);
    struct ListNode* rhead = reverseList(mid);

    while (rhead)
    {
        if (head->val != rhead->val)
            return false;

        head = head->next;
        rhead = rhead->next;
    }

    return true;

}